In the next two chapters we want to present some subsets of REC. To
define them we show some different types of tiling systems. The following is
called unambiguous tiling system and was 1992 introduced by D. Giammarresi
and A. Restivo in~\cite{giammarresi1992recognizable}. This kind of tiling
system describes a tiling system which uses an injective function between a
picture and its local picture. Formally, an unambiguous tiling system is
described in the following:
\begin{definition}
A tiling system $(\Sigma, \Gamma, \Theta, \pi)$ is \emph{unambiguous} if and
only if for any picture $p \in L, L \subseteq \Sigma^{*,*}$, there exists at
most one local picture $q \in LOC(\Theta)$ such that $p = \pi(q)$.
\end{definition}
We can call a picture language $L \in REC$ an unambiguous picture language iff
it admits an unambiguous tiling system $(\Sigma, \Gamma, \Theta, \pi)$. The family
of all unambiguous recognizable picture languages is denoted by UREC.

Our next definition describes a tiling system which is introduced to separate
the picture language families UREC and DREC. DREC is the family of all
deterministic recognizable picture languages. This kind of tiling system is
called $d$-unambiguous tiling system, where $d = \{l2r, r2l, t2b, b2t\}$ is a
set of scanning directions. For example, $l2r$ is the scanning direction of a
picture column by column from left to right. That means that a pixel of a
picture can only be read if any pixel in the column to the left was read. These tiling systems were introduced in 2007 by M. Anselmo, D.
Giammarresi and M. Madonia in~\cite{anselmo2007recognizable}. Formally, a
$l2r$-unambiguous tiling system is described in the following.
\begin{definition}
A tiling system $(\Sigma, \Gamma, \Theta, \pi)$ is \emph{$l2r$-unambiguous} if
for any local column $col \in \Gamma^{m,1} \cup \{\#\}^{m,1}$, and column picture
$p \in \Sigma^{m,1}$, there exists at most one local column $col' \in
\Gamma^{m,1}$ such that $p = \pi(col')$ and $B_{2,2}\left(\{\#\}^{1,2} \vcat
(col \hcat col') \vcat \{\#\}^{1,2}\right) \subseteq \Theta$.
\end{definition}
Informally we can say a $l2r$-unambiguous tiling system recognizes a picture from
left to right column by column and there is only one possible next local column.

A language is \emph{$column$-unambiguous} if it is recognized by a
$d$-unambiguous tiling system for some $d \in \{l2r,r2l\}$ and it is
\emph{$row$-unambiguous} if it is recognized by an $e$-unambiguous tiling system
for some $e \in \{t2b, b2t\}$.
The family of all $column$-unambi-guous languages and the family of all
$row$-unambiguous are denoted by $Col$-UREC and $Row$-UREC respectively.

Let $L_{fr = fc} = \{p \in \Sigma^{*,*} \mid l_1(p) = l_2(p) \text{ and }
p(1, i) = p(i, 1) \text{ for } 1 \leq i \leq l_1(p)\}$ be the language of
squares over a two-letters alphabet $\Sigma = \{a, b\}$ where the first row is
equal to the first column. Please note that $L_{fr = fc} \in REC$. Let's regard
an example of an $l2r$-unambiguous tiling system which recognizes $L_{fr = fc}$.
\begin{example}
$T = (\Sigma, \Gamma, \Theta, \pi)$ is a tiling system, where 
\begin{compactitem}
  \item $\Gamma = \{{x}_{y}^{z}$ with $x, y \in \Sigma, z \in \{0, 1, 2\}\}$,
  \item $\pi({x}_{y}^{z}) = x$ and
  \item $0$ describes a position below the diagonal, $1$ a position on the
  diagonal and $2$ a position above the diagonal.
\end{compactitem}
\label{unambiguousTilingSystemExample}
\end{example}
For a better visualization of the language $L_{fr=fc}$ and the tiling system $T$, an example of a picture $p \in L_{fr=fc}$ together with the
corresponding local picture $p'$ can be found below.
\begin{center}
\begin{tabular}{lr}
$p = $ \begin{tabular}{|D{0.38cm}|D{0.38cm}|D{0.38cm}|D{0.38cm}|D{0.38cm}|}
\hline
 $a$ & $a$ & $b$ & $b$ & $a$ \tabularnewline
\hline
 $a$ & $b$ & $b$ & $a$ & $a$ \tabularnewline
\hline
 $b$ & $b$ & $a$ & $a$ & $b$ \tabularnewline
\hline
 $b$ & $b$ & $a$ & $a$ & $a$ \tabularnewline
\hline
 $a$ & $a$ & $a$ & $a$ & $b$ \tabularnewline
\hline
\end{tabular}
&
$p' = $ \begin{tabular}{|D{0.38cm}|D{0.38cm}|D{0.38cm}|D{0.38cm}|D{0.38cm}|}
\hline
 ${a}_{a}^{1}$ & ${a}_{a}^{2}$ & ${b}_{b}^{2}$ & ${b}_{b}^{2}$ & ${a}_{a}^{2}$\tabularnewline
\hline
 ${a}_{a}^{0}$ & ${b}_{a}^{1}$ & ${b}_{b}^{2}$ & ${a}_{b}^{2}$ & ${a}_{a}^{2}$\tabularnewline
\hline
 ${b}_{b}^{0}$ & ${b}_{b}^{0}$ & ${a}_{b}^{1}$ & ${a}_{b}^{2}$ & ${b}_{a}^{2}$\tabularnewline
\hline
 ${b}_{b}^{0}$ & ${b}_{b}^{0}$ & ${a}_{b}^{0}$ & ${a}_{b}^{1}$ & ${a}_{a}^{2}$\tabularnewline
\hline
 ${a}_{a}^{0}$ & ${a}_{a}^{0}$ & ${a}_{a}^{0}$ & ${a}_{a}^{0}$ & ${b}_{a}^{1}$\tabularnewline
\hline
\end{tabular}
\end{tabular}
\end{center}

To understand how the tiling system $T$ works we informally want to describe a
generation process of a picture. For any local column $col \in \Gamma^{m,1}$,
and any column picture $p \in \Sigma^{m,1}$, the local column $col' \in
\Gamma^{m,1}$, is unambiguously determined as follows: If $i$ is a position at
the diagonal of an input picture in column $col$ then $col(i,1) =
{x'}_{y'}^{1}$. Let $p(i+1,1) = x$ and $p(1,1) = y$. It follows that $col'$
is ${x}_{y}^{1}$ at position $(i + 1, 1)$. For all positions $j$ above the
diagonal position $i + 1$ from $col'$, $col'(j, 1) = {x}_{y}^{2}$ iff $p(j,
1) = x$ and $p(1, 1) = y$. For all positions $k$ below the diagonal position
$i + 1$, $col'(k, 1) = x_{y}^{0}$ iff $p(k, 1) = x$ and $col(k, 1) =
{x'}_{y}^{0}$.

We can see $T$ is $l2r$-unambiguous and hence $L_{fr=fc} \in$ $Col$-UREC.
Similarly we can show that $T$ is $r2l$, $t2b$ and $b2t$-unambiguous. That
implies that $L_{fr=fc}$ is in $Row$-UREC.

Next we want to look at the closure properties of the family
UREC. First I. M\"{a}urer shows in~\cite{maurer2006weighted} that
\begin{theorem}
UREC is closed under projection and disjoint union.
\end{theorem}
In~\cite{anselmo2006unambiguous} M. Anselmo, D. Giammarresi, M. Madonia,
and A. Restivo proved that
\begin{theorem}
UREC is closed under intersection and rotation.
\end{theorem}
\begin{theorem}
UREC is not closed under horizontal and vertical concatenation and under
horizontal and vertical concatenation closure.
\end{theorem}
\begin{proof}
That was proved in~\cite{anselmo2006unambiguous}. In the proof it was shown
that the language $L_{fc = lc}$ which contains pictures where the first column
is equal to the last one is in UREC. The language $L_{c = c'} = \Sigma^{*,*}
\hcat L_{fc = lc} \hcat \Sigma^{*,*}$ of pictures with two equal columns is not
in UREC. This implies the non-closure of horizontal concatenation. The other
non-closure properties can be proved similarly. 
\end{proof}
Let's talk about the family dependencies.
\begin{theorem}
UREC $\subset$ REC.
\end{theorem}
M. Anselmo, D. Giammarresi, M. Madonia and A. Restivo proved this theorem
in~\cite{anselmo2006unambiguous}. In this proof it was shown that $L_{c = c'}
\in REC$ but $L_{c = c'} \not \in UREC$.
The following theorem was proved by M. Anselmo, D. Giammarresi and M.
Madonia in~\cite{anselmo2007recognizable}.
\begin{theorem}
$Col$-UREC $\cap$ $Row$-UREC $\subset$ $Col$-UREC $\cup$ $Row$-UREC $\subset$
UREC.
\end{theorem}
To prove that $Col$-UREC $\cap$ $Row$-UREC $\subset$ $Col$-UREC $\cup$
$Row$-UREC it was shown that the language $L_2 = L_{fc = c'} \cap L_{c' = lc}
\cap S$ is in $Row$-UREC but not in $Col$-UREC. Where $L_{fc = c'}$ is the language of
pictures $p$ where the first column is equal to one column $i \in \{2, 3,
\ldots, l_1(p)\}$. $L_{c' = lc}$ is the language of pictures $p$ where a column $i \in
\{1, 2, \ldots, l_1(p) - 1\}$ is equal to the last column. $S$ is the language
of square pictures. $L_3 = L_{fc = c'} \cap L_{c' = lc} \cap L_{fr = r'} \cap L_{r'
= lr}$ is the language which separates $Col$-UREC $\cup$ $Row$-UREC and UREC.
$L_{fc = c'}$ is  similar to $L_{fr = r'}$ and $L_{c' = lc}$ is similar to
$L_{r' = lr}$ the only difference is that we regard the rows and not the
columns.
\label{urec}